The present disclosure relates to a fast motion estimation apparatus and method based on adaptive search range and partial matching error, and more particularly, to a fast motion estimation apparatus and method, which determine a matching block corresponding to the original block of one image frame from among the candidate blocks of another image frame and estimate a motion vector between two image frames.
Motion Estimation (ME) denotes finding a motion vector on the basis of pixels from one image frame to another image frame. Motion estimation is used for effectively eliminating temporal redundancy and compressing video. Block-based motion estimation techniques including MPEG-x and 11.26x search the most appropriate matching block called the optimal block in a given search range.
A full search algorithm is an optimal block matching technique for finding the most appropriate motion vector, but requires an excessive amount of calculation. Several methods have been proposed which decrease a search range (fast search) or reduce the number of pixels in block matching between the original block and a candidate block for decreasing the calculative complexity of the full search algorithm. That is, motion estimation is largely divided into a search operation and a matching operation. Moreover, each operation is divided into a loss approach and a lossless approach according to whether a coding efficiency is the same or degraded in comparison with the existing full search algorithm.
In a fast search algorithm, a loss algorithm reduces the number of test target points in a given window, and includes three-step search, four-step search and multi-resolution technique. A lossless algorithm includes Successive Elimination Algorithm (SEA), Multi-level SEA (MSEA) and improved MSEA thereof. The SEA removes unnecessary calculation in a block averaging operation, and the MSEA uses a scheme similar to that of the SEA but can remove more calculation. The improved MSEA has been developed by expanding the MSEA for effectively finding ineffective blocks.
In a fast matching algorithm, a loss approach is for reducing calculation on the Sum of Absolute Difference (SAD) of each candidate block. A loss algorithm may be divided into pixel decimation pattern, sub-sampling and sorting-based technique. Recently, a prediction-based algorithm has been proposed, and can save the considerable cost for calculation.
A lossless fast matching approach is a fast processing approach that does not damage the quality of an encoded image, and may be combined with another fast lossless search approach such as the SEA. A Partial Distortion Elimination (PDE) algorithm is an example of fast search. The PDE algorithm scans a given window region by lines from an upper end to a lower end in a raster scheme. In the same scheme, a block matching error, i.e., SAD is calculated by lines even in block matching. By comparing with previously-calculated minimum SAD for each line (for example, sixteen pixels), the elimination of a candidate block is determined. Through such an approach, unnecessary candidate blocks may be eliminated in advance before SAD calculation on all candidate blocks is completed.
Many improved approaches based on PDE have been proposed and show good results. In such approaches, a common operation is one that divides the original block into smaller units (for example, line, sub-block and pixel) to calculate the complexity of each of the units, sorts the calculated complexity in descending power, and compares it with a candidate block for each period (for example, eight pixels or sixteen pixels) in a given window region. However, improved PDE approaches still require a much amount of calculation for the calculation of SAD, and moreover, when a candidate block is similar to the original block but is not the optimal block in the final stage, the improved PDE approaches still require time for removing the candidate block.
Accordingly, even in the case of loss fast motion estimation that causes only the negligible deterioration of quality, it may be a useful means that decreases an amount of calculation necessary for SAD calculation and increases a processing speed in time, and thus the development of a motion estimation technique using it is required.